Dusza towarzystwa
Limit pamięci: 32 MB
W remizie strażackiej w Bajtycy-Zdroju odbywa się impreza, na którą przybyły
tłumy okolicznych mieszkańców. Organizowane są liczne zabawy, przed każdą z
nich chłopcy dobierają się w pary z dziewczętami tak, by stworzyć jak
największą liczbę par. Do jednej pary dobierają się jedynie takie dwie osoby,
które znają się wzajemnie. To pozwala nam wprowadzić kluczowe dla tego zadania
pojęcie:
Definicja.
Duszą towarzystwa nazywamy osobę, której wyjście z imprezy spowoduje, że
maksymalna możliwa do utworzenia liczba par chłopców i dziewcząt zmaleje.
Za chwilę ma się odbyć kolejna zabawa, jednak powstał problem. Do remizy
przyszła o jedna osoba więcej niż pozwalają przepisy przeciwpożarowe. Trzeba
więc znaleźć kogoś, kto w zamian za darmową wejściówkę na wszystkie kolejne
imprezy w tym sezonie zgodzi się wrócić już do domu. Strażacy szybko
postanowili, że wszystkie dusze towarzystwa lepiej zapytać w drugiej
kolejności. Pomóż im i wyznacz wszystkie dusze towarzystwa obecne w remizie.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się trzy liczby
całkowite , i (, ), oznaczające odpowiednio liczbę chłopców i dziewcząt oraz liczbę
znajomości pomiędzy nimi. Chłopców i dziewczęta numerujemy kolejnymi liczbami
całkowitymi, począwszy od . W kolejnych wierszach znajdują się opisy
znajomości. Każdy z tych wierszy zawiera dwie liczby całkowite i
(, ), które oznaczają, że chłopiec
i dziewczę znają się wzajemnie.
Wyjście
Na standardowe wyjście wypisz numery wszystkich osób, które są duszami
towarzystwa, w osobnych wierszach. Najpierw należy wypisać numery chłopców, a
następnie numery dziewcząt. Obydwie listy numerów powinny być posortowane
rosnąco.
Przykład
Dla danych wejściowych:
4 4 4
2 1
3 2
4 3
4 4
poprawną odpowiedzią jest:
2
3
4
1
2
Autor zadania: Jakub Łącki (poniekąd zapożyczenie).